package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;

/**
 * fuck，弄半天这个 left 和 right 是从第 left 节点反转到 right 节点，不是当 val = left 反转到 val = right
 *
 * @author qidi
 * @date 2021-12-27 14:25:48
 */
class Q0092_ReverseLinkedListIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (left == right) return head;

            // 新的头
            ListNode nh = new ListNode();
            nh.next = head;
            ListNode cur = nh;
            // 左起点
            ListNode lstart = null;
            // 左终点
            ListNode lend = null;
            int i = 0;
            boolean flag = false;

            while (cur != null) {
                if (i == right) {
                    flag = true;
                }
                ListNode next = cur.next;

                if (lstart == null && i + 1 == left) {
                    lstart = cur;
                } else {
                    if (lstart != null) {
                        if (lend == null) {
                            lend = cur;
                        } else {
                            cur.next = lstart.next;
                        }
                        lstart.next = cur;
                    }
                }
                cur = next;
                i++;
                if (flag) break;
            }
            if (lend != null) lend.next = cur;

            return nh.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0092_ReverseLinkedListIi().new Solution();
        ListNode head;
        head = ListUtil.getInstance().generateFromArray(new int[]{3, 5});
        solution.reverseBetween(head, 1, 2);
        head = ListUtil.getInstance().generateFromArray(new int[]{1, 2, 3, 4, 5});
        solution.reverseBetween(head, 2, 4);
        head = ListUtil.getInstance().generateFromArray(new int[]{1, 2, 3, 4, 5});
        solution.reverseBetween(head, 1, 4);
    }
}